/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class FloodFill {
	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		if (image == null || image.length == 0) {
			return image;
		}
		int n = image.length;
		int m = image[0].length;
		boolean[][] visited = new boolean[n][m];
		int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
		int oldColor = image[sr][sc];
		influence(image, sr, sc, newColor, oldColor, visited, dir);
		return image;
	}

	private void influence(int[][] image, int sr, int sc, int newColor, int oldColor, boolean[][] visited,
			int[][] dir) {
		visited[sr][sc] = true;
		image[sr][sc] = newColor;
		for (int[] is : dir) {
			int x = sr + is[0];
			int y = sc + is[1];
			if (x >= 0 && x < image.length && y >= 0 && y < image[0].length && oldColor == image[x][y]
					&& !visited[x][y]) {
				influence(image, x, y, newColor, oldColor, visited, dir);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] images = { { 1, 1, 1 }, { 1, 1, 0 }, { 1, 0, 1 } };
		System.out.println(new FloodFill().floodFill(images, 1, 1, 2));
		for (int[] is : images) {
			for (int i = 0; i < is.length; i++) {
				System.out.print(is[i] + " ");
			}
			System.out.println();
		}
	}

}
